package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/22 11:17 星期一
 */
public class _695_岛屿的最大面积 {

    public static void main(String[] args) {
        int[][] grid = new int[][]{{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0}, {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
//        int[][] grid = new int[][]{{0,0,0,0,0,0,0,0}};
        System.err.println(maxAreaOfIsland(grid));
    }

    public static int maxAreaOfIsland(int[][] grid) {
        //初始化
        int max = 0;
        //当遍历未超出边界，一切继续
        for (int sr = 0; sr < grid.length; sr++) {
            for (int sc = 0; sc < grid[sr].length; sc++) {
                if (grid[sr][sc] == 1){
                    //是岛屿，深度优先递归
                    max = Math.max(dfs(grid, sr, sc),max);
                }
            }
        }
        return max;
    }

    public static int dfs(int[][] grid, int sr, int sc) {
        //若超出边界或为海水，退出dfs
        if (sr < 0 || sc < 0 || sr >= grid.length || sc >= grid[0].length || grid[sr][sc] == 0){
            return 0;
        }
        //让岛屿被淹没（防止重复查找）
        grid[sr][sc] = 0;
        //岛屿块数+1
        int cnt = 1;
        //四个方向深优
        cnt+=dfs(grid,sr+1,sc);
        cnt+=dfs(grid,sr-1,sc);
        cnt+=dfs(grid,sr,sc+1);
        cnt+=dfs(grid,sr,sc-1);
        //返回cnt计数，就是当前这个岛屿数
        return cnt;
    }
}
